package com.gxc.array;

/**
 * 3011. 判断一个数组是否可以变为有序
 * 给你一个下标从 0 开始且全是 正 整数的数组 nums 。
 *
 * 一次 操作 中，如果两个 相邻 元素在二进制下数位为 1 的数目 相同 ，
 * 那么你可以将这两个元素交换。你可以执行这个操作 任意次 （也可以 0 次）。
 *
 * 如果你可以使数组变有序，请你返回 true ，否则返回 false
 */
public class CanSortArray {

    public static void main(String[] args) {
        System.out.println(handle(new int[]{1,256,64}));
    }

    public static boolean handle(int[] nums) {
        int[] number = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            number[i] = getOneAmount(nums[i]);
        }
        int slow = 0;
        int fast = 0;
        int slowMax = 0;
        int fastMin = Integer.MAX_VALUE;
        boolean flag = true;
        while (fast < nums.length) {
            if (number[slow] == number[fast]) {
                fastMin = Math.min(fastMin, nums[fast]);
                flag = true;
                fast++;
            } else {
                if (flag) {
                    if (slowMax > fastMin) return false;
                    //重置大小
                    flag = false;
                    fastMin = Integer.MAX_VALUE;
                }
                slowMax = Math.max(slowMax, nums[slow]);
                slow++;
            }

        }
        if (slowMax > fastMin) return false;
        return true;
    }

    public static int getOneAmount(int num) {
        int res = 0;
        int divisor = 256;
        while (num!=0) {
            res = res + num/divisor;
            num = num % divisor;
            divisor = divisor/2;
        }
        return res;
    }

    //不适用额外空间
    public static boolean handle2(int[] nums) {
        int curGroupMax = 0;
        int lasGrouptMax = 0;
        int curCnt = 0;
        int lastCnt = 0;
        for (int i = 0; i < nums.length; i++) {
            //二进制1的数量
            curCnt = Integer.bitCount(nums[i]);
            if (lastCnt == curCnt) {
                curGroupMax = Math.max(curGroupMax, nums[i]);
            } else {
                //如果 二进制1的数量  不一样。则比较
                lasGrouptMax = curGroupMax;
                lastCnt = curCnt;
                curGroupMax = nums[i];
            }
            if (nums[i] < lasGrouptMax) return false;
        }
        return true;
    }

    /**
     * 不适用额外空间
     */
    class Solution {
        public boolean canSortArray(int[] nums) {
            int lastCnt = 0;
            int lastGroupMax = 0;
            int curGroupMax = 0;
            for (int num : nums) {
                int curCnt = Integer.bitCount(num);
                if (curCnt == lastCnt) {
                    curGroupMax = Math.max(curGroupMax, num);
                } else {
                    lastCnt = curCnt;
                    lastGroupMax = curGroupMax;
                    curGroupMax = num;
                }
                if (num < lastGroupMax) {
                    return false;
                }
            }
            return true;
        }
    }

}
